Fibonicci Calculation through Dynamic Multi Threading

int fibonacci(int n){

if(n<2) return n;

else return fibonacci(n-1)+fibonacci(n-2);

}

위의 고전적인 재귀함수를 이용할 경우(without Dynamci Programming)

다항함수를 넘어서는 기하급수적으로 커지는 시간복잡도를 가지게 된다.

#include <iostream>

#include <thread>

static int ThreadCounter=0;

int ThreadFibonacci(int n, int* ret){

if(n<2){

*ret=n;

return *ret;

}

else{

int tmp1, tmp2;

ThreadCounter++;

std::thread x(ThreadFibonacci, n-1, &tmp1); // Spawn

int y=ThreadFibonacci(n-2, &tmp2);

x.join(); // Sync

*ret=tmp1+y;

return *ret;

}

int main(void){

std::cout<<"Concurrency: "<<std::thread::hardware_concurrency()<<std::endl;

int result=0;

int dump=ThreadFibonacci(20, &result);

std::cout<<result<<'\n';

std::cout<<"Thread Called Counter(Total): "<<ThreadCounter<<std::endl;

return 0;

}

재귀함수 내에 스레드 Spawn이 들어갈 경우, 컴퓨터 시스템에서 사용할 수 있는 스레드 개수를 넘어갈 수 있다.

thread constructor failed: Resource temporarily unavailable

About M1 MacBook Pro approximately 25,000 threads can used

계산 Dag(Calculation Dag)

멀티스레드 프로그램을 의해 실행되는 멀티스레드 계산을 방향성 비순한 그래프 G=(V, E)로 나타낸다(계산 Dag)

(u,v)=∈E $(u, v)=\in E$ 는 연산 u가 v보다 이전에 실행되어야 하나는 명령어 간의 종속성을 뜻한다.

만일 u에서 v까지의 방향성 경로를 가진 경우 "(논리적) 직렬 방법에 포함된다.” 라고 부르며,

그러지 않을 경우 "(논리적) 병렬 방법에 포함된다.” 라고 부른다.

성능 측정(Evaluate) Work & Span 작업: T1 $T_1$ 범위: T∞ $T_\infty$ 작업 법칙 Tp≥T1/P $T_p\geq T_1/P$ 범위 법칙 TP≤T∞ $T_P\leq T_\infty$ 속도 향상(SpeedUp) T1/TP $T_1/T_P$ 속도 향상은 작업 법칙에 따라 T1/TP≤P $T_1/T_P\leq P$ 를 항상 만족한다. 속도 향상은 범위 법칙에 따라 T1/T∞ $T_1/T_\infty$ 는 멸티스레드 계산의 병렬성(parallelism)을 제공한다. (최대 속도 향상의 한계점; Limitation of Parallel Calculation) TP≤T1/P+T∞ $T_P\leq T_1/P+T_\infty$

#include <iostream>

#include <thread>

#include <vector>

using namespace std;

void TF(vector<int> x, vector<int> y, int* ret){

assert(x.size()==y.size());

for(int i=0; i<x.size(); ++i) *ret+=x[i]*y[i];

}

vector<int> MatVec(vector<vector<int>> A, vector<int> x){

int n=A.size();

vector<int> y(n);

vector<thread> threads;

for(int i=0; i<n; ++i) y[i]=0;

for(int i=0; i<n; ++i){

threads.push_back(thread(TF, A[i], x, &y[i]));

}

for(int i=0; i<n; ++i) threads[i].join();

return y;

}

int main(void){

vector<vector<int>> A={

{1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 4, 5, 6, 7, 8, 9},

{1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 4, 5, 6, 7, 8, 9}

};

vector<int> x={9, 8, 7, 6, 5, 4, 3, 2, 1};

vector<int> y=MatVec(A, x);

for(int i=0; i<y.size(); ++i) std::cout<<y[i]<<' ';

std::cout<<std::endl;

return 0;

}

경쟁 조건

멀티스레드 알고리즘에 대해서 같은 입력에 대해 항상 같은 작업을 수행하면 결정적이라고 한다.

수행에 따라 동작이 달라지는 경우 비결정적이라고 한다.

멀티스레드 알고리즘은 “결정성 경쟁”이 포함되어 있기 때문에 실패할 수도 있다.

결정성 경쟁(Race)는 논리적으로 병렬인 명령어 두 개가 같은 메모리 장소를 접근하거나,

명령어 중 적어도 하나가 쓰기를 하려고 하는 경우에 발생한다.

#include <iostream>

#include <thread>

#include <vector>

using namespace std;

void append100(int* x){

for(int i=0; i<1000; ++i) *x+=10;

}

void ThreadRace(void){

int x=0;

vector<thread> threads;

for(int i=0; i<3; ++i){

threads.push_back(thread(append100, &x));

}

for(int i=0; i<3; ++i) threads[i].join();

std::cout<<"Expected X: 30000\nGet X: "<<x<<std::endl;

}

int main(void){

ThreadRace();

return 0;

}

Expected X: 30000

Get X: 22400

위와 같이 일정 비율로 옳지 않은 값을 리턴함

하나의 + 연산이더라도, 어셈블리어나 기계어 관점에서는 기본적으로

Memory->Register(READ)

Add

Register->Memory(WRITE)

연산으로 나누어져있다.

경쟁을 고려해서 코드를 적절하게 짜는 것은 매우 어렵고 불가능하다.

경쟁을 대처하기 위해 상호배제 잠금 등을 이용하여,

각 스레드간의 독립성과 결정적 경쟁을 가지지 않도록 설계해야 함

Dynamic Multi Thread Algorithm